1.3 归纳总结 思维拓展

归纳总结

本章的重点是分析程序的时间复杂度。一定要掌握分析时间复杂度的方法和步骤, 很多读者在做题时一眼就能看出程序的时间复杂度, 但就是无法规范地表述其推导过程。为此, 编者查阅众多资料, 总结出了此类题型的两种形式, 供大家参考。

1. 循环主体中的变量参与循环条件的判断

在用于递推实现的算法中,首先找出基本运算的执行次数 $x$ 与问题规模 $n$ 之间的关系式,解得 $x=f\left(n\right),f\left(n\right)$ 的最高次幂为 $k$ ,则算法的时间复杂度为 $O\left(n^k\right)$ 。例如,

例1：

int i =1;
    while(i<n)
        i=i*2;

例2：

int y = 5;
    while((y+1)*(y+1)<n)
        y=y+1;

在例 1 中,设基本运算 i = i * 2 的执行次数为 $t$ ,则 $2^t\le n$ ,解得 $t\le {\log }_{2}n$ ,故 $T\left(n\right)=O\left({\log }_{2}n\right)$ 。

在例 2 中,设基本运算 y=y+1 的执行次数为 $t$ ,则 $t=y-5$ ,且 $\left(t+5+1\right)\left(t+5+1\right)<n$ ,解得 $t<\sqrt{n}-6$ ,即 $T\left(n\right)=O\left(\sqrt{n}\right)$ 。

2. 循环主体中的变量与循环条件无关

此类题可采用数学归纳法或直接累计循环次数。多层循环时从内到外分析, 忽略单步语句、 条件判断语句, 只关注主体语句的执行次数。此类问题又可分为递归程序和非递归程序:

• 递归程序一般使用公式进行递推。时间复杂度的分析如下:

$$T\left(n\right)=1+T\left(n-1\right)=1+1+T\left(n-2\right)=\cdots =n-1+T\left(1\right)$$

即 $T\left(n\right)=O\left(n\right)$ 。

• 非递归程序的分析比较简单, 可以直接累计次数。本节前面给出了相关的习题。

思维拓展

求解斐波那契数列

$$F\left(n\right)=\{\begin{array}{ll}0,& n=0\\ 1,& n=1\\ F\left(n-1\right)+F\left(n-2\right),& n>1\end{array}$$

有两种常用的算法: 递归算法和非递归算法。试分别分析两种算法的时间复杂度 (提示: 请结合归纳总结中的两种方法进行解答)。